package srcInterviewPrep;

public final class FindInSortedMatrix
{
    public static boolean DivideAndConquerFind(
        int[][] matrix,
        int elem,
        int x0,
        int y0,
        int x1,
        int y1)
    {
        if (x1 < x0
            || y1 < y0)
        {
            return false;
        }
        
        int xMid = (x0 + x1)/2;
        int yMid = (y0 + y1)/2;
        
        if (matrix[xMid][yMid] == elem)
        {
            System.out.println(String.format("(%d, %d)", xMid, yMid));
            return true;
        }
        else if (elem < matrix[xMid][yMid])
        {
            return (DivideAndConquerFind(matrix, elem, x0, y0, xMid, yMid - 1)
                    || DivideAndConquerFind(matrix, elem, xMid + 1, y0, x1, xMid - 1)
                    || DivideAndConquerFind(matrix, elem, x0, yMid - 1, xMid - 1, y1));
        }
        else
        {
            return (DivideAndConquerFind(matrix, elem, xMid + 1, y0, x1, yMid)
                    || DivideAndConquerFind(matrix, elem, x0, yMid + 1, xMid - 1, y1)
                    || DivideAndConquerFind(matrix, elem, xMid, yMid + 1, x1, y1));
        }
    }
    
    public static boolean FindDiagonal(
            int[][] matrix,
            int elem,
            int xMax,
            int yMax)
        {
            int x = 0;
            int y = yMax - 1;
            
            while (x < xMax && y > 0)
            {
                if (elem == matrix[x][y])
                {
                    System.out.println(String.format("(%d, %d)", x, y));
                    return true;
                }
                else if (elem > matrix[x][y])
                {
                    ++x;
                }
                else
                {
                    --y;
                }
            }
            
            return false;
        }
}
